#! /usr/bin/env python
##
# Script for PicoCTF Broadcast challenge
# Created by Amos (LFlare) Ng
##
# Define the variables we have
e = 3 
c1 = 261345950255088824199206969589297492768083568554363001807292202086148198450506273465213103176917308775904515781859685219364772648314531521917440109254237008730103285165770468539312932564510693762285993836665784246027325189716812638318129149401564978255988878053290556777956323156437328191504477621921004555576
n1 = 1001191535967882284769094654562963158339094991366537360172618359025855097846977704928598237040115495676223744383629803332394884046043603063054821999994629411352862317941517957323746992871914047324555019615398720677218748535278252779545622933662625193622517947605928420931496443792865516592262228294965047903627
c2 = 147535246350781145803699087910221608128508531245679654307942476916759248221617357178122807825995929323954427881577467131564256357567176635921165037361398930124955353554547117274249383564511567505927944298770509702152760325152321848037114630824955318219237316599699769841766840111897950181152716166822846684065
n2 = 405864605704280029572517043538873770190562953923346989456102827133294619540434679181357855400199671537151039095796094162418263148474324455458511633891792967156338297585653540910958574924436510557629146762715107527852413979916669819333765187674010542434580990241759130158992365304284892615408513239024879592309 
c3 = 633230627388596886579908367739501184580838393691617645602928172655297372055633123093311400868519857733638616918187630133150020343726118984627791555369599350014240671224476573355208797883735497454442310035676436540938840414797670521334361253044288175343106610733033491028210009679975045541658549239962617172197
n3 = 1204664380009414697639782865058772653140636684336678901863196025928054706723976869222235722439176825580211657044153004521482757717615318907205106770256270292154250168657084197056536811063984234635803887040926920542363612936352393496049379544437329226857538524494283148837536712608224655107228808472106636903723

# Join ciphertext and n exponents in list
c = [c1, c2, c3]
n = [n1, n2, n3]

# Define some functions to help shorten this annoying process
def inv_pow(x, n):
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1
 
def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a / b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1

def crt(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
 
    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod

m = crt(n, c)
raw_m_hex = str(hex(inv_pow(m,3)))
m_hex = raw_m_hex[2:-1]
print("Flag: %s" % m_hex.decode('hex'))